package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.LinkedProblem;

/**
 * 翻转链表
 *
 * @author tzp
 * @since 2020/10/16
 */
public class LC234_reverse implements LinkedProblem {
    /**
     * 翻转链表第from到第to个节点
     * 0-base include边界
     *
     * @param from >=0, <to
     * @param to   >from, <Integer.Max
     * @return 正常情况下传入的head保持不变还是head, 但是如果from是0的话就不对了, 所以最后判断了一下.
     */
    public ListNode reverse(ListNode head, int from, int to) {
        ListNode cur = head, pre = null,
                newHeadPre = null, newHead = null;//既有newHeadPre又有newHead, 是为了统一处理from=0的情况
        int i = 0;
        while (cur != null) {
            if (i < from) {
                pre = cur;
                cur = cur.next;
            } else if (i == from) {
                newHeadPre = pre;
                newHead = cur;
                pre = cur;
                cur = cur.next;
                if (newHeadPre != null) newHeadPre.next = null;//断链, 可有可无
            } else if (i > from && i <= to) {//这4行和LC206的核心四行是一模一样的
                pre.next = cur.next;
                cur.next = newHead;
                newHead = cur;
                cur = pre.next;
            } else {
                break;
            }
            i++;
        }
        if (newHeadPre != null) newHeadPre.next = newHead;
        return from == 0 ? newHead : head;
    }

    public static void main(String[] args) {
        ListNode a;

        a = ListNode.arrayToListNode(new int[]{0, 1, 2, 3, 4, 5, 6, 7});
        System.out.println(new LC234_reverse().reverse(a, 0, 4));

        a = ListNode.arrayToListNode(new int[]{0, 1, 2, 3, 4, 5, 6, 7});
        System.out.println(new LC234_reverse().reverse(a, 2, 4));

        a = ListNode.arrayToListNode(new int[]{0, 1, 2, 3, 4, 5, 6, 7});
        System.out.println(new LC234_reverse().reverse(a, 2, 9));

    }
}
